// https://www.lintcode.com/problem/peak-index-in-a-mountain-array/

public class Solution {
    /**
     * @param A: an array
     * @return: any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
     */
    public int peakIndexInMountainArray(int[] A) {
        // Write your code here
        // 二分法，找到一个满足比左右元素都大的元素即可。
        int left = 0, right = A.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < A[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}